package com.nanbei.avl;

import com.nanbei.tree.TreeNode;

/**
 * @ClassDescription: AVL树
 * @JdkVersion: 17
 * @Author: BaoShan.Li
 * @Date: 2024/6/2 23:04
 */
public class AVLNode {
    int key;
    Object val;
    AVLNode left;
    AVLNode right;
    int height = 1;

    public AVLNode(int key) {
        this.key = key;
    }

    public AVLNode(int key, Object val) {
        this.key = key;
        this.val = val;
    }

    public AVLNode(int key, Object val, AVLNode left, AVLNode right) {
        this.key = key;
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public int getHeight(AVLNode avlNode) {
        return avlNode == null ? 0 : avlNode.height;
    }


    //更新avl树的高度 （删除、更新、旋转）
    public void updateHeight(AVLNode avlNode) {
        avlNode.height = Integer.max(getHeight(avlNode.left), getHeight(avlNode.right)) + 1;
    }

    // 平衡因子 （左子树高度 - 右子树高度）
    // -1、0、1 表示平衡 、 >1 或 <-1 表示不平衡
    // >1 表示 左边的树高。 <-1 表示右边的树高
    public int bf(AVLNode avlNode){
        return getHeight(avlNode.left) - getHeight(avlNode.right);
    }

    /**
     * LL
     * 示例：需要旋转的树
     *          8
     *        / ： \
     *       6  ：  9
     *      / \ ：
     *     5   7
     *    /
     *   4
     * avl树右旋
     * 将要旋转的树的根节点计为 parent
     * parent的左节点计为 node
     * node.right 视为要移动的节点
     * @param parent 需要旋转的节点
     * @return 旋转后的节点
     */
    public AVLNode rightRotate(AVLNode parent){
        // 先获取根节点的左子树
        AVLNode node = parent.left;
        // 获取左子树的右子树 然后赋值给根节点的左孩子
        parent.left = node.right;
        // 最后将左子树的右节点指向根节点
        node.right = parent;
        // 更新节点高度的位置不能互换
        // 更新根节点的高度
        updateHeight(parent);
        // 左右旋转的时候 node节点的高度会发生变化 需更新
        updateHeight(node);

        return node;
    }

    /**
     * RR
     * 示例：需要旋转的树
     *          2
     *        / ： \
     *       1  ：  4
     *          ： / \
     *           3    5
     *                 \
     *                  7
     * avl树左旋
     * @param parent 需要旋转的节点
     * @return 旋转后的根节点
     */
    public AVLNode leftRotate(AVLNode parent){
        // 先获取根节点的右子树
        AVLNode node = parent.right;
        // 获取右子树的左子树 然后赋值给根节点的左孩子
        parent.right = node.left;
        // 最后将左子树的右节点指向根节点
        node.right = parent;
        // 更新节点高度的位置不能互换
        // 更新根节点的高度
        updateHeight(parent);
        // 左右旋转的时候 node节点的高度会发生变化 需更新
        updateHeight(node);
        return node;
    }

    /**
     * LR： 先左旋在右旋
     * 示例：
     *        6
     *      /   \
     *     2     7
     *    / \
     *   1   4
     *      / \
     *     3   5
     *  先左旋左子树
     *  子右旋根节点
     *  第一次左旋后的结果为：
     *        6
     *      /   \
     *     4     7
     *    / \
     *   2   5
     *  / \
     * 1  3
     * @param parent 需要旋转的节点
     * @return 旋转后的根节点
     */
    public AVLNode leftRightRotate(AVLNode parent){
        // 1. 先左旋左子树
        parent.left = leftRotate(parent.left);
        // 2. 在右旋根节点
        return rightRotate(parent);
    }

    /**
     * RL
     * 示例：
     *        2
     *      /   \
     *     1     6
     *          / \
     *         4   7
     *        / \
     *       3   5
     * 第一次右旋后的结果为：
     *        2
     *      /   \
     *     1     4
     *          / \
     *         3   6
     *            / \
     *           5   7
     *
     * @param parent 需要旋转的节点
     * @return 旋转后的根节点
     */
    public AVLNode rightLeftRRotate(AVLNode parent){
        // 1. 先右旋右子树
        parent.right = rightRotate(parent.right);
        // 2. 在左旋根节点
        return leftRotate(parent);
    }

    /**
     * 检查node节点时候失衡
     * 问题： 在下列的LL和RR 中为什么会出现等于
     * 答： 在删除节点的时候例如
     *      6
     *    /   \
     *   3     8
     *  / \
     * 1   5
     * 当把 8 节点删除的时候 就会出现根节点左子树bf==0的情况
     * @param node 检查的根节点
     * @return  平衡后的节点
     */
    public AVLNode balance(AVLNode node) {
        if (node == null) {
            return null;
        }

        int bf = bf(node);
        if (bf > 1 && bf(node.left) >= 0) { // LL
            return rightRotate(node);
        } else if (bf > 1 && bf(node.left) < 0) { //LR
            return leftRightRotate(node);
        } else if (bf < -1 && bf(node.right) > 0) { //RL
            return rightLeftRRotate(node);
        } else if (bf < -1 && bf(node.right) <= 0) { //RR
            return leftRotate(node);
        }
        return node;

    }
}
